package array;

import java.util.Objects;

/**
 * <h1>动态数组</h1>
 *
 * @author wangkaiqi
 */
public class DynamicArray<T> {
    private T[] data;
    private int size;

    /**
     * 根据传入容量，构造 Array
     */
    public DynamicArray(int capacity) {
        data = (T[]) new Object[capacity];
        size = 0;
    }

    public DynamicArray() {
        this(10);
    }

    // 获取数组容量
    public int getCapacity() {
        return data.length;
    }

    // 获取数据元素个数
    public int getSize() {
        return size;
    }

    //判断当前数组是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    //修改 index 位置的元素
    public void set(int index, T value) {
        checkIndex(index);
        data[index] = value;
    }

    // 获取对应 index 位置的元素
    public T get(int index) {
        checkIndex(index);
        return data[index];
    }

    // 查看数组是否包含指定元素
    public boolean contains(T value) {
        for (int i = 0; i < size; i++) {
            if (value.equals(data[i])) {
                return true;
            }
        }
        return false;
    }

    // 获取对应元素的下标，未找到，返回 -1
    public int find(T value) {
        for (int i = 0; i < size; i++) {
            if (Objects.equals(data[i], value)) {
                return i;
            }
        }
        return -1;
    }

    // 在 index 位置，插入元素 e，时间复杂度 O(m+n)
    public void add(int index, T value) {
        checkIndexForAdd(index);
        // 如果当前元素个数等于数组容量，则将数组扩容未原来的 2 倍
        if (data.length == size) {
            resize(data.length * 2);
        }
        // 将 [index,size) 位置的元素往后移动一位
        for (int i = size; i > index; i--) {
            data[i] = data[i - 1];
        }
        data[index] = value;
        size++;
    }
    //

    /**
     * <h2>扩容方法，时间复杂度 O(n)</h2>
     */
    private void resize(int capacity) {
        T[] newData = (T[]) new Object[capacity];

        //将旧数组元素移动到新数组
        for (int i = 0; i < size; i++) {
            newData[i] = data[i];
        }
        data = newData;
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Require index >=0 and index < size");
        }
    }

    private void checkIndexForAdd(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Require index >=0 and index < size");
        }
    }
}
